Any two points P.sub.1 =(x.sub.1, y.sub.1) and P.sub.2 =(x.sub.2, y.sub.2) in a cartesian space lie on a straight line. Interpolating to find the coordinates of any point P =(x, y) on the line between these two points may be done using the equation of a line given by: ##EQU2##
From Equation (1), it is obvious that an interpolation may be performed by three subtraction operations [(x-x.sub.1),(x.sub.2 -x.sub.1),(y.sub.2 -y.sub.1 )] followed by a division, a subsequent multiplication and an eventual addition. Binary division and multiplication are generally performed by shift-and-add/subtract respectively shift-and-add operations. To increase throughput, the operation steps are usually pipelined, and the operations have latches between operation steps.
The invention accomplishes the merging of the division and multiply operations resulting in an increased performance compared to a division pipeline followed by a multiply pipeline. In a particular stage of the merged divide/multiply operator, the division part produces a quotient bit which is immediately used as the multiplicant bit in the multiply part.
In Gouraud shading, a technique applicable in color raster scan displays, the color intensity along the edge of a polygon is interpolated from the intensity at the endpoints. The intensity at the pixels within the polygon is interpolated from the intensity values at the ends of horizontal lines running from one edge to another. The invention speeds up the operation of the described bi-linear interpolator.
For example, consider the operation: EQU A.times.(B/C)
A flow diagram of the conventional approach used to process this operation is shown in FIG. 1. In a conventional process, the division of B and C would be handled in a serial manner with each bit of the quotient, d.sub.o, d.sub.1 . . . d.sub.n, temporarily stored in block D=B/C. After the quotient has been stored in D, the operation of A.times.D is carried out, again in a step-by-step process where each bit "d" of the quotient D is multiplied by A to obtain the final result A.times.B/C.
The procedure as illustrated in FIG. 1 above may be contrasted with the approach applying the principles of the invention by comparison with FIG. 2. FIG. 2 shows an illustrative flow diagram of the scheme of the invention doing the same multiplication and division. As is illustrated in FIG. 2, the division B/C is carried out in parallel with the multiplication A.times.(B/C). Each bit of the quotient, d.sub.o - - - d.sub.n, is multiplied as it is produced at each stage of the division. No temporary storage of the quotient is required. Thus, the calculation of interpolation values is carried out in an extremely fast manner in contrast to the prior art.